import java.util.*;

/**
 * @author hewei
 * @version 1.0
 * @description: 1054. 距离相等的条形码
 * @date 2022/10/24 15:41
 */

public class RearrangeBarcodes {

    public int[] rearrangeBarcodes1(int[] barcodes) {
        int n = barcodes.length;
        int[] ans = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
        }
        for (Integer i : map.keySet()) {
            heap.add(i);
        }
        int index = 0;
        while (!heap.isEmpty()) {
            Integer poll = heap.poll();
            Integer count = map.get(poll);
            ans[index++] = poll;
            --count;
            while (count > 0) {
                Integer poll1 = heap.poll();
                ans[index++] = poll1;
                map.put(poll1, map.get(poll1) - 1);
                if (map.get(poll1) != 0) heap.add(poll1);
                ans[index++] = poll;
                --count;
            }
        }
        return ans;
    }

    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] cnt = new int[10001];
        for (int barcode : barcodes) {
            cnt[barcode]++;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10001; i++) {
            if (cnt[i] != 0) list.add(i);
        }
        list.sort((a, b) -> cnt[b] - cnt[a]);
        int[] temp = new int[barcodes.length];
        int index = 0;
        for (Integer a : list) {
            for (int i = 0; i < cnt[a]; i++) {
                temp[index++] = a;
            }
        }
        int[] ans = new int[barcodes.length];
        index = 0;
        for (int i = 0; i < barcodes.length; i += 2) {
            ans[i] = temp[index++];
        }
        for (int i = 1; i < barcodes.length; i += 2) {
            ans[i] = temp[index++];
        }
        return ans;
    }
}
